let arr = [1, 7, 4, 2, 6, 9, 3, 8, 5]
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }

  let s = Math.floor(arr.length / 2)
  // temp = arr.splice(s, 1)[0]
  let temp = arr.splice(s, 1)[0]
  console.log('temp', temp)

  let left = []
  let right = []
  
  for (let i = 0; i < arr.length; i++) {
    // if (arr[i] < arr[s]) {
    if (arr[i] < temp) { // 不能再用arr[s]了 因为原数组已经把那一项删除了
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }

  }
  
  console.log('left', left)
  console.log('right', right)

  return quickSort(left).concat(temp, quickSort(right))
}


console.log(quickSort(arr))